package testOne2Ten;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * 根据前序，中序重建二叉树
 * 根据后序，中序重建二叉树
 * Created by Wongy on 2018/3/13.
 */
public class Test6 {
    private static TreeNode rebuildByPreAndIn(int[] pre, int[] in) {
        if (pre == null || in == null || pre.length <= 0 || in.length <= 0 || pre.length != in.length) {
            return null;
        }
        TreeNode treeNode = new TreeNode(pre[0]);
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                treeNode.left = rebuildByPreAndIn(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                treeNode.right = rebuildByPreAndIn(Arrays.copyOfRange(pre, i + 1, in.length), Arrays.copyOfRange(in, i + 1, in.length));
            }
        }
        return treeNode;
    }

    private static TreeNode rebuildByInAndSuf(int[] in, int[] suf) {
        if (suf == null || in == null || suf.length <= 0 || in.length <= 0 || suf.length != in.length) {
            return null;
        }
        TreeNode treeNode = new TreeNode(suf[suf.length - 1]);
        for (int i = 0; i < in.length; i++) {
            if (in[i] == suf[suf.length - 1]) {
                treeNode.left = rebuildByInAndSuf(Arrays.copyOfRange(in, 0, i), Arrays.copyOfRange(suf, 0, i));
                treeNode.right = rebuildByInAndSuf(Arrays.copyOfRange(in, i + 1, in.length), Arrays.copyOfRange(suf, i, in.length - 1));
            }
        }
        return treeNode;
    }


    public static void main(String[] args) {
        int[] pre = {1, 2, 4, 7, 3, 5, 6, 8};
        int[] in = {4, 7, 2, 1, 5, 3, 8, 6};
        int[] suf = {7, 4, 2, 5, 8, 6, 3, 1};
//        TreeNode treeNode = reConstructBinaryTree(pre, in);
//        preOrder(treeNode);
        TreeNode treeNode1 = rebuildByPreAndIn(pre, in);
        preOrder(treeNode1);
        System.out.println();
        TreeNode treeNode2 = rebuildByInAndSuf(in, suf);
        preOrder(treeNode2);
    }

    private static void preOrder(TreeNode treeNode) {
        if (treeNode == null) {
            return;
        }
        preOrder(treeNode.left);
        System.out.print(treeNode.value + " ");
        preOrder(treeNode.right);
    }
}

class TreeNode {
    TreeNode left;
    TreeNode right;
    int value;

    public TreeNode(int value) {
        this.value = value;
    }
}
